"""
230. 二叉搜索树中第K小的元素
给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。

 

示例 1：


输入：root = [3,1,4,null,2], k = 1
输出：1
示例 2：


输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3
"""
try:
    from binarytree import Node as TreeNode
    from binarytree import tree
except:
    ...
finally:
    ...
    from typing import Optional


class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        """
        思路：使用中序遍历，保存遍历结果在数组里，然后直接读取数组的第k号元素即可。
        """
        inorder = self._inorder(root)
        return inorder[k - 1]

    def _inorder(self, root: Optional[TreeNode]) -> int:
        res = []
        stack = []
        node = root

        while stack or node:
            while node:
                stack.append(node)
                node = node.left
            node = stack.pop()
            res.append(node.val)
            node = node.right
        return res


if __name__ == "__main__":
    my_tree = tree()
    print(my_tree)
    s = Solution()
    print(s.kthSmallest(my_tree, 1))
